package forkjoinpool;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.TimeUnit;

/**
 * @description: 快排
 * @author: WangPengPeng
 * @create: 2021-11-27 21:22
 **/
public class Demo1 {

    static class SortTask extends RecursiveAction {
        final long[] array;

        final int low;
        final int high;

        public SortTask(long[] array) {
            this.array = array;
            this.low = 0;
            this.high = array.length - 1;
        }

        public SortTask(long[] array, int low, int high) {
            this.array = array;
            this.low = low;
            this.high = high;
        }

        // 找到分割点 partition 然后 partition左边的值都小于他，右边的值 都大于他
        private int partition (long[] array,int low,int high) {
            long x = array[high];
            int i = low - 1;
            for (int j = low; j < high; j++) {
                if (array[j] <= x) {
                    i++;
                    swap(array,i,j);
                }
            }
            swap(array,i + 1,high);

            return i + 1;
        }

        private void swap(long[] array, int i, int j) {
            if (i != j) {
                long temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        @Override
        protected void compute() {
            if (low < high) {
                // 找到分区的元素下标
                int pivot = partition(array, low, high);
                // 将数组分为两部分
                SortTask left = new SortTask(array, low, pivot - 1);
                SortTask right = new SortTask(array, pivot + 1, high);

                left.fork();
                right.fork();
                left.join();
                right.join();
            }
        }


    }

    public static void main(String[] args) throws InterruptedException {
        long[] array = {5, 3, 7, 9, 2, 4, 1, 8, 10};
        SortTask sortTask = new SortTask(array);
        ForkJoinPool pool = new ForkJoinPool();
        pool.submit(sortTask);
        pool.shutdown();

        pool.awaitTermination(10, TimeUnit.SECONDS);
        System.out.println(Arrays.toString(array));

    }
}
